package chapter_04;

// 解析算术表达式


/*
直接解析算术表达式还是相当困难的，因此分两步实现算法更为容易：
1. 将算术表达式转换为另一种形式：后缀表达式。
2. 计算后缀表达式的值。
 */


/*
后缀表达式
日常算术表达式是将操作符（operator）（+、-、*、/）放在两个操作数（数字，或
代表数字的字母）之间的。因为操作符写在操作数的中间，所以才把这种写法称为中缀表达法。
在后缀表达式中[也称作波兰逆序表达式，或者RPN]，操作符跟在两个操作数的后面。这样，
A+B就成为AB+，A/B成为AB/。更糟的中缀表达式同样可以转换成后缀表达式。

中缀表达式和后缀表达式
中缀表达式                   后缀表达式
A+B-C                       AB+C-
A*B/C                       AB*C/
A+B*C                       ABC*+
A*B+C                       AB*C+
A*(B+C)                     ABC+*
A*B+C*D                     AB*CD*+
(A+B)*(C-D)                 AB+CD-*
((A+B)*C)-D                 AB+C*D-
A+B*(C-D/(E+F))             ABCDEF+/-*+
 */


/*
把中缀表达式转换为后缀表达式
从左至右读取中缀表达式，顺序地查看每一个字符。在此过程中，将这些操作数和操作符
复制到后缀表达式输出的字符串中。关键是要知道每个字符该何时输出。
如果中缀字符串中的字符是操作数，则立即把它复制到后缀字符串中。这就是说，如果看到
中缀字符串中的A时，就立即把A写到后缀字符串里，一定不要延迟；读到操作数就复制它们，
而不去管多久后才能复制和它们关联的操作符。
决定何时复制操作符更复杂一些，但它的规则和计算中缀表达式一样。一旦可以利用操作符
求中缀表达式某部分的值，就把该运算符复制到后缀字符串中。

将A+B*C转换成后缀表达式
从中缀表达式      分解中缀表达式过程       求后缀表达式过程        注释
中读取的字符
A               A                       A
+               A+                      A
B               A+B                     AB
-               A+B-                    AB+     读到-，可以把+复制到后缀表达式字符串中
C               A+B-C                   AB+C
End             A+B-C                   AB+C-   看到表达式末端时，可复制-

将A+B*C转换成后缀表达式
从中缀表达式      分解中缀表达式过程       求后缀表达式过程        注释
中读取的字符
A               A                       A
+               A+                      A
B               A+B                     AB
*               A+B*                    AB      读到*，*比+优先级高，还不能复制过来
C               A+B*C                   ABC     看到C后，可复制*
                A+B*C                   ABC*
End             A+B*C                   ABC*+   看到表达式末端时，可复制+

将A*(B+C)转换成后缀表达式
从中缀表达式      分解中缀表达式过程       求后缀表达式过程        注释
中读取的字符
A               A                       A
*               A*                      A
(               A*(                     A
B               A*(B                    AB      因为有括号，所以不能复制*
+               A*(B+                   AB
C               A*(B+C                  ABC     仍不能复制+
)               A*(B+C)                 ABC+    看到)时，可复制+
                A*(B+C)                 ABC+*   复制完+后，可复制*
End             A*(B+C)                 ABC+*   完毕
在数字求值过程中，需要向前和向后两个方向来扫描中缀表达式，以完成后缀表达的转换。
当某个操作符后面的操作符优先级更高或者为左括号时，就不能把这个操作符输出到后缀表达字符
串中。如果真的是如上这种情况，高优先级别的操作符或括号中的操作符必须要比低优先级的操作符
更早写入到后缀表达字符串中。

在栈中保存操作符
可以看到从中缀到后缀的转换过程中，操作符的顺序是颠倒的。因为第一个操作符必须等到第二个
操作符输出后才能输出，所以操作符在后缀字符串中的顺序和中缀字符串中的顺序是相反的。

将A+B*(C-D)转换为后缀表达式
从中缀表达式      分解中缀表达式过程       求后缀表达式过程    栈中的内容
中读取的字符
A               A                       A
+               A+                      B                   +
B               A+B                     AB                  +
*               A+B*                    AB                  +*
(               A+B*(                   AB                  +*(
C               A+B*(C                  ABC                 +*(
-               A+B*(C-                 ABC                 +*(-
D               A+B*(C-D                ABCD                +*(-
)               A+B*(C-D)               ABCD-               +*(
                A+B*(C-D)               ABCD-               +*(
                A+B*(C-D)               ABCD-               +*
                A+B*(C-D)               ABCD-*              +
                A+B*(C-D)               ABCD-*+

从某方面来说，由栈中弹出数据项实际上能向后（从右向左）扫描输入字符串。我们并没有扫描
整个输入字符串，而只是检查操作符和括号。它们在读输入串的时候已经被压入栈中，所以现在
可以通过栈逆序重调用它们。
操作数（A，B等等）在中缀和后缀表达法中出现的顺序是相同的，因此可以读到操作数的时候就
输出它们；它们不需要存储在栈里。

转换规则
下面把中缀到后缀表达法的规则更明确地表示出来。从中缀表达式输入字符串中读取数据项，然
后按下表显示的操作进行处理。
在这个表中，<和>=符号表示操作符之间的优先级关系，而不是数值的比较关系。opThis是刚刚
从中序表达式中读到的操作符，而opTop是刚刚出栈的操作符。
从输入（中缀表达式）中读取的字符            动作
操作数                                 写至输出（postfix）
左括号(                                推其入栈
右括号)                                栈非空时，重复以下步骤
                                      弹出一项，
                                      若项不为(，则写至输出
                                      若为(则退出循环
Operator(opThis)                      若栈为空，
                                      推opThis
                                      否则，
                                      栈非空时，重复
                                      弹出一项
                                      若为(，推其入栈，或
                                      若项为operator(opTop)，且
                                      若opTop<opThis，推入opTop，或
                                      若opTop>=opThis，输出opTop
                                      若opTop<opThis则退出循环，或项为(
                                      推入opThis
没有更多项                             当栈非空时，
                                      弹出项目，将其输出

后缀表达式求值
从后缀表达式中读取的元素                    执行的动作
操作数                                      入栈
操作符                               从栈中提出两个操作数，用操作符将其执行运算。结果入栈。
全部做完之后，退栈就可以得到答案了，后缀表达式求值就结束了。
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StackExpression {
    private int maxSize;
    private char[] stackArray;
    private int top;

    public StackExpression(int s) {
        maxSize = s;
        stackArray = new char[maxSize];
        top = -1;
    }

    public void push(char j) {
        stackArray[++top] = j;
    }

    public char pop() {
        return stackArray[top--];
    }

    public char peek() {
        return stackArray[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }

    public char peekN(int n) {
        return stackArray[n];
    }

    public void displayStack(String s) {
        System.out.print(s);
        System.out.print("Stack {bottom --> top}: ");
        for (int j = 0; j < size(); j++) {
            System.out.print(peekN(j));
            System.out.print(' ');
        }
        System.out.println();
    }
}


class InToPost {
    private StackExpression theStack;
    private String input;
    private String output = "";

    public InToPost(String in) {
        input = in;
        int stackSize = input.length();
        theStack = new StackExpression(stackSize);
    }

    public String doTrans() {
        for (int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            theStack.displayStack("For " + ch + " ");
            switch (ch) {
                case '+':           // it's + or -
                case '-':
                    gotOper(ch, 1);     // go pop operators
                    break;                  // (precedence 1)
                case '*':           // it's * or /
                case '/':
                    gotOper(ch, 2);
                    break;
                case '(':
                    theStack.push(ch);
                    break;
                case ')':
                    gotParen(ch);
                    break;
                default:
                    output = output + ch;
                    break;
            }
        }
        while (!theStack.isEmpty()) {
            theStack.displayStack("While ");
            output = output + theStack.pop();
        }
        theStack.displayStack("End  ");
        return output;
    }

    public void gotOper(char opThis, int prec1) {
        while (!theStack.isEmpty()) {
            char opTop = theStack.pop();
            if (opTop == '(') {
                theStack.push(opTop);
                break;
            } else {
                int prec2;

                if (opTop == '+' || opTop == '-')
                    prec2 = 1;
                else
                    prec2 = 2;
                if (prec2 < prec1) {
                    theStack.push(opTop);
                    break;
                } else
                    output = output + opTop;
            }
        }
        theStack.push(opThis);
    }

    public void gotParen(char ch) {
        while (!theStack.isEmpty()) {
            char chx = theStack.pop();
            if (chx == '(')
                break;
            else
                output = output + chx;
        }
    }
}


class InfixApp {
    public static void main(String[] args) throws IOException {
        String input, output;
        while (true) {
            System.out.print("Enter infix: ");
            System.out.flush();
            input = getString();
            if (input.equals(""))
                break;

            InToPost theTrans = new InToPost(input);
            output = theTrans.doTrans();
            System.out.println("Postfix is " + output + '\n');
        }
    }

    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }
}
